//
// Created by daiyizheng on 2022/4/12.
//

#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;
class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
            unordered_set<string> dict(wordDict.begin(), wordDict.end());
        return dfs(s, dict, 0);
    }

    vector<string> dfs(string s, unordered_set<string> wordDict, int i){
        vector<string> res;
        if(i==s.length()){
            res.push_back("");
            return res;
        }

        for (int end = i+1; end <=s.length(); ++end) {
            string word = s.substr(i, end-i);
            if(!wordDict.count(word))continue;
            vector<string> list = dfs(s, wordDict, end);
            for (string str:list){
                string split = str==""?"":" ";
                res.push_back(word+split+str);
            }
        }
        return res;
    }
};